package com.mccken.practice.top100.Top_1$20.Top_22;

import com.mccken.practice.top100.ListNode;

/**
 * @program: mccken-collect
 * @description:
 * @author: mccken
 * @create: 2024-01-24 14:12
 **/
public class IsPalindrome3 {
	private ListNode endOfFirstHalf(ListNode head){
		ListNode fast = head;
		ListNode slow = head;
		
		while (fast.next != null && fast.next.next != null) {
			fast = fast.next.next;
			slow = slow.next;
		}
		return slow;
	}
	
	private ListNode reverseList(ListNode head) {
		ListNode prev = null;
		ListNode curr = head;
		
		while (curr != null) {
			ListNode next = curr.next;
			curr.next = prev;
			prev = curr;
			curr = next;
		}
		return prev;
	}
	
	public boolean isPalindrome(ListNode head) {
		if (head == null) {
			return true;
		}
		// 找到前半部分链表的尾结点，反转后半部分链表
		ListNode firstHalfEnd = endOfFirstHalf(head);
		ListNode secondHalfStart = reverseList(firstHalfEnd.next);
		boolean result = true;
		
		ListNode p1 = head;
		ListNode p2 = secondHalfStart;
		while (result && p2 != null) {
			if (p1.val != p2.val) {
				result = false;
			}

			p1 = p1.next;
			p2 = p2.next;
		}
		// 注意，还要恢复回来
		firstHalfEnd.next = reverseList(secondHalfStart);
		return result;
	}
	
}


